# 作业一
# n = input()
# n = int(n)
# list = []
# i = 0
# out = 0
# list = input().split()
# list = [int(v) for v in list]
# list.sort()
# # print(list)
# for v in list:
#     i += 1
# if (i == n):
#     i = 0
#     for v in list:
#         i += 1
#         if (i <= (n + 1) // 2):
#             v = int(v)
#             # print(v)
#             out += (v + 1) // 2
#             # print(out)
#         else:
#             break
#     print(out)

# 作业二 合并

# list = []
# list = input().split()
# list = [int(v) for v in list]
# # print(list)
# a = list[0]
# b = list[1]
# # print(a, b)
# a = str(a)
# b = str(b)
# len_a = len(a)
# len_b = len(b)
# # print(len_a, len_b)
# # print(type(a), type(b))
# if (len_a <= 5 and len_b <= 5):
#     out = ''
#     flag = 1
#     for i in range(0, len_a + len_b):
#         if (flag == 1):
#             if (len_a - 1 < i // 2):
#                 flag = 0
#                 break
#             else:
#                 out += a[i // 2]
#                 flag = 0
#         elif (flag == 0):
#             if (len_b - 1 < i // 2):
#                 flag = 1
#                 break
#             else:
#                 out += b[i // 2]
#                 flag = 1
#         if (i == len_a + len_b - 1):
#             flag = 2
#     if (flag == 1):
#         i -= len_b
#         while i < len_a:
#             out += a[i]
#             i += 1
#     elif (flag == 0):
#         i -= len_a
#         while i < len_b:
#             out += b[i]
#             i += 1
#     print(out)

# 作业三 素数
# import math
#
# num = int(input())
# list = [2]
# if num > 2:
#     for i in range(3, num + 1):
#         for j in range(2, int(math.sqrt(i)) + 1):
#             if i % j == 0:
#                 break
#         else:
#             list.append(i)
# i = 0
# for i in range(0, len(list)):
#     print(list[i], end="")
#     if i != len(list) - 1:
#         print(" ", end="")

#作业四 统计成绩
# count = int(input())
# list = input().split()
# # print(list)
# list = [int(v) for v in list]
# # print(list)
# leng = len(list)
# if count == leng:
#     total = 0
#     pass_count = 0
#     for i in range(0, leng):
#         total += list[i]
#         if list[i] >= 60:
#             pass_count += 1
#     average = total / count
#     print("average =", round(average, 1))
#     print("count =", pass_count)

# 作业五 查字典
# n = int(input())
# if (n <= 1000) and (n > 0):
#     dict = dict()
#     for i in range(0 , n):
#         list = input().split()
#         dict[list[1]] = list[0]
#     # print(dict)
#     while 1:
#         ch = input()
#         if ch == 'dog':
#             break
#         r = dict.get(ch)
#         if r != None:
#             print(r)
#         else:
#             print('dog')
# 作业六 集合运算
# n_a = int(input())
# a = input().split()
# n_b = int(input())
# b = input().split()
# if len(a) == n_a and len(b) == n_b:
#     a = [int(v) for v in a]
#     b = [int(v) for v in b]
#     # print(a)
#     # print(b)
#     i = list(set(a).intersection(set(b)))
#     i.sort()
#     # print(i)
#     u = list(set(a).union(set(b)))
#     u.sort()
#     # print(u)
#     d = list(set(a).difference(set(b)))
#     d.sort()
#     # print(d)
#     for v in i:
#         print(v, end=" ")
#     print(end='\n')
#     for v in u:
#         print(v, end=" ")
#     print(end='\n')
#     for v in d:
#         print(v, end=" ")
# 作业七 页面置换
# nm = input().split()
# n = int(nm[0])
# m = int(nm[1])
# count = 0
# if (n >= 1) and (n <= 500) and (m >= 1) and (m <= 500):
#     list = list()
#     l = input().split()
#     l = [int(v) for v in l]
#     for i in range(0, m):
#         if l[i] < 1 or l[i] > m:
#             exit(0)
#         else:
#             length = len(list)
#             if length == 0:
#                 list.append(l[i])
#                 count += 1
#             else:
#                 if list.count(l[i]) == 1:
#                     if list[0] != l[i]:
#                         list.remove(l[i])
#                         list.insert(0, l[i])
#                 else:
#                     list.insert(0, l[i])
#                     count += 1
#                     if len(list) > n:
#                         list.pop()
#     print(count)
#     # print(list)
#     list.sort()
#     for i in range(0, n):
#         print(list[i], end=" ")
# 作业八 插入排序
# n = int(input())
# if n < 1 or n > 1000:
#     exit(0)
# list = input().split()
# list = [int(v) for v in list]
# if len(list) != n:
#     exit(0)
# for i in range(1, n):
#     # print(i, end=" ")
#     num = list[i]
#     for j in range(0, i):
#         if num < list[j]:
#             list.pop(i)
#             list.insert(j, num)
#             break
#     for j in range(0, n-1):
#         print(list[j], end=" ")
#     print(list[n-1])
# 作业九  字符串去除并排序
# s = input()
# list = list()
# while 1:
#     list.append(s[0])
#     s = [x for x in s if x != s[0]]
#     if len(s) == 0:
#         break
# list.sort()
# r = "".join(list)
# print(r)